The invention relates generally to the field of computer graphics, and more particularly to systems and methods for generating pixel values for pixels in the image.
In computer graphics, a computer is used to generate digital data that represents the projection of surfaces of objects in, for example, a three-dimensional scene, illuminated by one or more light sources, onto a two-dimensional image plane, to simulate the recording of the scene by, for example, a camera. The camera may include a lens for projecting the image of the scene onto the image plane, or it may comprise a pinhole camera in which case no lens is used. The two-dimensional image is in the form of an array of picture elements (which are variable termed xe2x80x9cpixelsxe2x80x9d or xe2x80x9cpelsxe2x80x9d), and the digital data generated for each pixel represents the color and luminance of the scene as projected onto the image plane at the point of the respective pixel in the image plane. The surfaces of the objects may have any of a number of characteristics, including shape, color, specularity, texture, and so forth, which are preferably rendered in the image as closely as possible, to provide a realistic-looking image.
Generally, the contributions of the light reflected from the various points in the scene to the pixel value representing the color and intensity of a particular pixel are expressed in the form of the one or more integrals of relatively complicated functions. Since the integrals used in computer graphics generally will not have a closed-form solution, numerical methods must be used to evaluate them and thereby generate the pixel value. Typically, a conventional xe2x80x9cMonte Carloxe2x80x9d method has been used in computer graphics to numerically evaluate the integrals. Generally, in the Monte Carlo method, to evaluate an integral                                           ⟨            f            ⟩                    =                                    ∫              0              1                        ⁢                                          f                ⁡                                  (                  x                  )                                            ⁢                              xe2x80x83                            ⁢                              ⅆ                x                                                    ,                            (        1        )            
where f(x) is a real function on the real numerical interval from zero to 1, inclusive, first a number xe2x80x9cNxe2x80x9d statistically-independent random numbers xi, i=1, . . . , N, are generated over the interval. The random numbers xi are used as sample points for which sample values f(xi) are generated for the function f(x), and an estimate {overscore (f)} for the integral is generated as                                           ⟨            f            ⟩                    ≈                      f            _                          =                              1            N                    ⁢                                    ∑                              i                =                1                            N                        ⁢                          xe2x80x83                        ⁢                                          f                ⁡                                  (                                      x                    i                                    )                                            .                                                          (        2        )            
As the number of random numbers used in generating the sample points f(xi) increases, the value of the estimate {overscore (f)} will converge toward the actual value of the integral  less than f greater than . Generally, the distribution of estimate values that will be generated for various values of xe2x80x9cN,xe2x80x9d that is, for various numbers of samples, of being normal distributed around the actual value with a standard deviation "sgr" which can be estimated by                               σ          =                                                    1                                  N                  -                  1                                            ⁢                              (                                                                            f                      2                                        _                                    -                                                            f                      _                                        2                                                  )                                                    ,                            (        3        )            
if the values xi used to generate the sample values f(xi) are statistically independent, that is, if the values xi are truly generated at random.
Generally, it has been believed that random methodologies like the Monte Carlo method are necessary to ensure that undesirable artifacts, such as Moire patterns and aliasing and the like, which are not in the scene, will not be generated in the generated image. However, several problems arise from use of the Monte Carlo method in computer graphics. First, since the sample points xi used in the Monte Carlo method are randomly distributed, they may not be generally evenly distributed across the interval, but instead may clump in various regions over the interval over which the integral is to be evaluated. Accordingly, depending on the set of random numbers which are generated, in the Monte Carlo method for significant portions of the interval there may be no sample points xi for which sample values f(xi) are generated. In that case, the error can become quite large. In the context of generating a pixel value in computer graphics, the pixel value that is actually generated using the Monte Carlo method may not reflect some elements which might otherwise be reflected if the sample points xi were guaranteed to be generally evenly distributed over the interval. This problem can be alleviated somewhat by dividing the interval into a plurality of sub-intervals, but it is generally difficult to determine a priori the number of sub-intervals into which the interval should be divided, and, in addition, in a multi-dimensional integration region (which would actually be used in computer graphics, instead of the one-dimensional interval described here) the partitioning of the region into sub-regions of equal size can be quite complicated.
In addition, since the method makes use of random numbers, the error |{overscore (f)}xe2x88x92 less than f greater than | (where |x| represents the absolute value of the value xe2x80x9cxxe2x80x9d) between the estimate value {overscore (f)} and actual value  less than f greater than is probabilistic, and, since the error values for various values of xe2x80x9cNxe2x80x9d are normal distributed around the actual value  less than f greater than , only sixty-eight percent of the estimate values {overscore (f)} that might be generated are guaranteed to lie within one standard deviation of the actual value  less than f greater than .
Furthermore, as is clear from equation (3), the standard deviation a decreases with increasing numbers of samples N, proportional to the reciprocal of square root of xe2x80x9cNxe2x80x9d (that is, 1/{square root over (N)}). Thus, if it is desired to reduce the statistical error by a factor of two, it will be necessary to increase the number of samples N by a factor of four, which, in turn, increases the computational load that is required to generate the pixel values, for each of the numerous pixels in the image.
Additionally, since the Monte Carlo method requires random numbers, an efficient mechanism for generating random numbers is needed. Generally, digital computers are provided with so-called xe2x80x9crandom numberxe2x80x9d generators, which are computer programs which can be processed to generate a set of numbers that are approximately random. Since the random number generators use deterministic techniques, the numbers that are generated are not truly random. However, the property that subsequent random numbers from a random number generator are statistically independent should be maintained by deterministic implementations of pseudo-random numbers on a computer.
The invention provides a new and improved computer graphics system and method for generating pixel values for pixels in the image using a strictly deterministic methodology for generating sample points for use in evaluating integrals defining aspects of the image.
In brief summary, the computer graphics system in accordance with the invention generates pixel values for pixels in an image of objects in a scene, using strictly-deterministic low-discrepancy sequences, illustratively Halton sequences, as sample points for evaluating integrals which are used to simulate a number of computer graphic techniques, including
(1) soft shadows generated for scenes illuminated by a light source having a finite extent, such as a disk, as opposed to a point light source;
(2) Simulation of depth of field;
(3) motion blur;
(4) jittering; and
(5) global illumination.
The computer graphics system uses the low-discrepancy sequences:
(1) in connection with soft shadows, to generate sample points over the finite extent of the light source illuminating the scene;
(2) in connection with simulation of depth of field, to generate sample points over the area of the lens between the scene and the image;
(3) in connection with motion blur, to generate sample points over a time interval over which motion blur is to be simulated for moving objects in the scene;
(4) in connection with jittering, to generate jittered sample points over an image or a plurality of contiguous pixels; and
(5) in connection with global illumination, to generate sample points for use in a strictly-deterministic Russian roulette methodology for generating estimators for use in simulating global illumination.
Unlike the random numbers used in connection with the Monte Carlo technique, the low discrepancy sequences ensure that the sample points are evenly distributed over a respective region or time interval, thereby reducing error in the image which can result from clumping of such sample points which can occur in the Monte Carlo technique. In particular, the invention facilitates the generation of images of improved quality when using the same number of sample points at the same computational cost as in the Monte Carlo technique.